//605 种花问题
/*
有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去

示例：
	输入：flowerbed = [1,0,0,0,1], n = 1
	输出：True
	输入：flowerbed = [1,0,0,0,1], n = 2
	输出：False

分析：
	flowerbed 数组，花的位置
	n  要放置的花数
*/
bool canPlaceFlowers(vector<int> &flowerbed, int n)
{
	//只有一个位置，且该位置为空，则种下去
	if (flowerbed.size() == 1 && flowerbed[0] == 0)
	{
		return --n <= 0; //放置了1朵花后，剩余有花，即 --n>0 时，不能放置所有的花，返回false。
	}
	//开始从第一盘花 的位置开始遍历
	for (int i = 0; i < flowerbed.size(); i++)
	{
		if (flowerbed[i] == 0)
		{ //该位置没有放置花
			if (i == 0)
			{ //左边界
				if (flowerbed[i + 1] == 0)
				{
					flowerbed[i] = 1; //放花
					n--;
				}
			}
			else if (i == flowerbed.size() - 1)
			{ //右边界
				if (flowerbed[i - 1] == 0)
				{
					flowerbed[i] = 1;
					n--;
				}
			}
			else
			{ //中间位置，左边没花，右边没花，则放置
				if ((flowerbed[i + 1] == 0) && (flowerbed[i - 1] == 0))
				{
					flowerbed[i] = 1;
					n--;
				}
			}
		}
	}
	return n <= 0; //到了最后，n
}

//可以考虑常数优化，在扫描数组 flowerbed 时，如果 count 的值已经达到 n，那么我们可以直接跳出循环并返回 True
bool canPlaceFlowers(int[] flowerbed, int n)
{
	int i = 0, count = 0;
	while (i < flowerbed.length)
	{
		if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0))
		{
			flowerbed[i++] = 1;
			count++;
		}
		if (count >= n)
			return true;
		i++;
	}
	return false;
}